Content Addressable Memory (CAM) is a type of memory that enables high-speed parallel searching of the memory for a desired data word. As such, CAMs may be used in search-intensive applications. FIG. 1 illustrates a conventional CAM 10. The CAM 10 includes a number of CAM cells 12 arranged into a number of CAM cell arrays 14-0 through 14-N, which are generally referred to herein collectively as CAM cell arrays 14 and individually as CAM cell array 14. Each of the CAM cells 12 is conventionally composed of a semiconductor memory cell (e.g., a Static Random Access Memory (SRAM) cell) and comparison circuitry. The CAM cell arrays 14-0 through 14-N store corresponding digital words having M+1 bits. In addition, the CAM cell arrays 14-0 through 14-N include corresponding valid bit circuitry 16-0 through 16-N, which are generally referred to herein collectively and individually as valid bit circuitry 16. For each CAM cell array 14, the corresponding valid bit circuitry 16 stores a bit value that represents a validity of the CAM cell array 14. The CAM 10 enables parallel searching of the CAM cell arrays 14-0 through 14-N for a desired digital word, i.e., search data, in a single clock cycle.
More specifically, in order to search the CAM 10, the search data is input into search line driver circuitry 18, which in turn outputs true and complementary logic values (CLT<0> through CLT<M> and CLC<0> through CLC<M>, respectively) onto corresponding search lines. For the search, in a low clock phase, match lines (MATCH LINE 0 through MATCH LINE N) connected to the CAM cell arrays 14-0 through 14-N, respectively, are precharged to a high voltage level (i.e., a logic “1”). Then, during a high clock phase, comparison circuitry of the CAM cells 12 compares the logic values on the corresponding search lines with corresponding data bits stored by the CAM cells 12. In this particular embodiment, the CAM cells 12 whose stored bit values do not match the logic values on the corresponding search lines operate to discharge the corresponding match lines to a low voltage level (i.e., a logic “0”). Thus, for example, if one of the CAM cells 12 in the CAM cell array 14-0 stores a “0” and the corresponding bit of the search data is a “1,” then that CAM cell 12 will pull MATCH LINE 0 low, thereby indicating that the digital word stored by that CAM cell array 14-0 does not match the search data. In addition, if the digital word stored by any of the CAM cell arrays 14 is invalid, the valid bit circuitry 16 for that CAM cell array 14 operates to pull the corresponding match line low. Thus, at the end of the high clock phase, only the match line(s) for the CAM cell array(s) 14 that stores a valid digital word that matches the search data remains high. Upon assertion of a latch clock (LATCH_CLK), the match lines (MATCH LINE 0 through MATCH LINE N) are latched by corresponding match line hold circuitry 20-0 through 20-N, which are generally referred to herein collectively and individually as match line hold circuitry 20.
One importation operation for CAMs such as the CAM 10 is referred to as a search and invalidate (search-invalidate) operation. In a search-invalidate operation, the CAM 10 is searched for the CAM cell array 14 (or possibly multiple CAM cell arrays 14) that stores a digital word that matches desired search data, and then that CAM cell array 14 is invalidated. Both the search and the invalidation are performed in a single clock cycle.
FIGS. 2A and 2B are a more detailed illustration of the conventional valid bit circuitry 16 and a corresponding timing diagram. For a search-invalidate operation, at a rising edge of a system clock (SYS_CLK), a comparison clock (COMPARE_CLK) is asserted to trigger the start of a compare process. During the compare process, if a valid bit cell 22 stores a valid bit, which in this case is a “1,” the valid bit cell 22 outputs a “1” to a NAND gate 24, which in turn outputs a “0” if both the output of the valid bit cell 22 and a TAG_MATCH input are “1.” The TAG_MATCH input is asserted to “1” when a digital word stored by the CAM cells 12 in the corresponding CAM cell may 14 matches the search data. As a result of the NAND gate 24 providing a “0” at its output, transistor 26 is disabled such that the corresponding match line is not discharged. Alternatively, if the valid bit cell 22 stores an invalid bit, which in this case is a “0,” the valid bit cell 22 outputs a “0” to the NAND gate 24, which in turn outputs a “1” to the transistor 26. At that point, the transistor 26 is activated by the “1” from the NAND gate 24, and transistor 28 is activated by the comparison clock. As a result, the match line is discharged.
Sometime after the rising edge of the system clock, a search-invalidate clock (SRINV_CLK) is asserted to trigger the start of an invalidate process. Preferably, by the time the search-invalidate clock is asserted, the comparison has completed, and a latch clock (LATCH_CLK) has already been asserted to latch the match line into the corresponding match line hold circuitry 20. During the invalidate process, an AND gate 30 compares the search-invalidate clock and the corresponding match line. Assuming that the match line is high at the end of the compare process, when the search-invalidate clock is asserted, the AND gate 30 outputs a logic “1,” which results in writing of an invalid bit value (e.g., a “0”) to the valid bit cell 22, thereby invalidating the CAM cell array 14. In contrast, if the match line is low at the end of the compare process, when the search-invalidate clock is asserted, the AND gate 30 outputs a logic “0” such that the invalid bit is not written to the valid bit cell 22, and the corresponding CAM cell array 14 remains valid.
Two parameters which govern the search-invalidate process are: (1) the invalidate process must not disturb a match indicator (i.e., hit) for the CAM cell array(s) 14 that stores a valid digital word that matches the search data and (2) the invalidate process must be given sufficient time to write the valid bit cell 22 of the CAM cell array(s) 14 to be invalidated. These two parameters are becoming increasingly difficult to meet and will soon be impracticable if not impossible to meet using the conventional valid bit circuitry 16 due to the continued scaling of CAMs to 28 nanometer (nm) processing technologies and beyond. More specifically, increased physical variations as a result of scaling may result in the invalidate process completing before the comparison has completed and the match line is latched by the match line hold circuitry 20. As a result, the invalidate process will disturb the match indicator for the corresponding CAM cell array 14 by pulling the corresponding match line low before it is latched by the match line hold circuitry 20. In addition, the increased physical variations may require an increase in the duration of the search-invalidate process (i.e., the SRINV_CLK) in order to ensure that the valid bit cell 22 is written. However, increasing the duration of the search-invalidate process means that there is less time available for the compare process to complete, which may result in CAM cell arrays 14 being erroneously validated or CAM cell arrays 14 that should be invalidated not being invalidated.
Therefore there is a need for a CAM, and more specifically valid bit circuitry for a CAM, that addresses the aforementioned issues.